The present invention relates generally to security apparatus for information processing systems and more particularly to apparatus for implementing an encryption algorithm without a complementarity property. The invention is particularly applicable to the secure transmission of scrambled television signals, although it is by no means limited to such use.
There are many schemes available for controlling the remote descrambling of television signals. Such schemes are necessary to maintain security in subscription television systems, including-cable television systems and satellite television systems. Typically, a system subscriber is provided with a descrambler connected between a television signal source (e.g., cable feed or satellite receiver) and a television set. Each subscriber's descrambler is remotely accessed by the system operator to enable or disable the receipt of specific services such as the Home Box Office movie channel or special pay-per-view sports events. One problem with such systems is that "pirates" are apt to break the system security and sell "black boxes" that enable the reception of all programming without paying for the services received. It has been difficult and expensive for system operators to contend with the piracy problem. Once a particular security system is breached, the system operator must usually replace all existing descramblers with new units that operate with a different security algorithm. This solution is not cost effective.
Various systems have been designed to make piracy more difficult. One such system is disclosed in U.S. Pat. No. 4,613,901 to Gilhousen, et al. entitled "Signal Encryption and Distribution System for Controlling Scrambling and Selective Remote Descrambling of Television Signals." In the Gilhousen, et al. system, a "working key" signal is generated in accordance with the well known DES security algorithm, after the algorithm is keyed by either a common category key signal or some other key signal. A unique encryption key stream is generated by processing an initialization vector signal in accordance with the DES algorithm when the algorithm is keyed by the working key signal. A television signal is scrambled in accordance with the unique encryption key stream to provide a scrambled television signal. A plurality of unique encrypted category key signals individually addressed to different selected subscribers' descramblers are generated by processing the initial common category key signal in accordance with the DES algorithm when the algorithm is keyed by a plurality of different "unit key" signals associated with different descramblers. The scrambled television signal, initialization vector signal, and plurality of encrypted category key signals are broadcast to the descramblers. At each descrambler, the encryption key stream is reproduced to descramble the television signal. Each descrambler has its unique unit key signal stored in memory for use in reproducing the common category key signal when the descrambler is addressed by its unique encrypted category key signal. By using the DES algorithm, the Gilhousen, et al. system provides a high level of security, making it difficult and expensive for a pirate to reproduce the working key.
The reliance on the DES algorithm by security systems such as Gilhousen, et al. renders such systems vulnerable to attack should the DES security ever be breached. Although no one has publicly broken the DES algorithm to date, a weakness has been discovered. The weakness stems from the "complementarity property" of encryption algorithms such as the DES algorithm. Although this weakness does not allow the algorithm to be broken, additional security would be provided, particularly in the key hierarchies disclosed by Gilhousen, et al., if the complementarity property were eliminated.
As a result of the complementarity property, the output of an encryption processor will be inverted if both the data and secure key input to the processor are inverted. This can be described mathematically as follows: EQU E.sub.K [X]=Y.fwdarw.E.sub.K [X]=Y
where
X is the data to be encrypted; PA1 K is the secure encryption key; and PA1 Y is the encrypted data.
Such complementarity is the only known property of DES that is remotely linear. Those skilled in the art will appreciate that the presence of a linear property in a security algorithm such as DES has the potential for compromising the security provided by the algorithm.
A detailed discussion of the DES algorithm can be found in Federal Information Processing Standards Publication 46 ("FIPS Pub. 46") issued by the National Bureau of Standards, United States Department of Commerce, "Announcing the Data Encryption Standard," Jan. 15, 1977 and FIPS Pub. 74, "Guidelines for Implementing and Using the NBS Data Encryption Standard," Apr. 1, 1981. Section 3.6 of FIPS Pub. 74, "Characteristics of the DES Algorithm," paragraph 4, lines 5-7, implicitly recognizes the complementarity property. The property is also mentioned in Davies, Donald W., "The Security of Data in Networks," IEEE Catalog No. EH0183-4, 1981, p. 7.
It would be advantageous to provide apparatus for implementing encryption algorithms without complementarity. Such encryption algorithms would include DES, as well as any other encryption or hashing function that possesses complementarity. The present invention provides such apparatus.